package binaryTree;

import java.util.ArrayList;
import java.util.HashMap;

import binaryTree.kthSmallest.Node;
import utils.binaryTreeUtil.TreeNode;

public class kthSmallest {
    ArrayList<Integer> list = new ArrayList<>();

    // 法一：中序遍历+list
    // 不可能重复，因为是二叉搜索树
    public int kthSmallest1(TreeNode root, int k) {
        inOrder1(root);
        return list.get(k - 1);
    }

    public void inOrder1(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder1(root.left);
        list.add(root.val);
        inOrder1(root.right);
    }

    // 法二：链表
    class Node {
        int val;
        Node next;

        public Node(int value) {
            val = value;
        }
    }

    Node head = null, tail = null;

    public int kthSmallest2(TreeNode root, int k) {
        inOrder2(root);
        Node curr = head;
        k--;
        while (k > 0) {
            curr = curr.next;
            k--;
        }
        return curr.val;
    }

    public void inOrder2(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder2(root.left);
        Node node = new Node(root.val);
        // 尾插法
        if (head == null) {
            head = node;
            tail = node;
        } else {
            tail.next = node;
            tail = node;
        }
        inOrder2(root.right);
    }

    public static void main(String[] args) {

    }
}
